package com.hiwhitley.leetcode.hard;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by hiwhitley on 16-12-28.
 */
public class RussianDollEnvelopes_354 {
    public static class Dot {
        private int w;
        private int h;

        public Dot(int w, int h) {
            this.w = w;
            this.h = h;
        }
    }

    public static class DotComparator implements Comparator<Dot> {
        @Override
        public int compare(Dot o1, Dot o2) {
            if (o1.w == o2.w) {
                return o2.h - o1.h;
            } else {
                return o1.w - o2.w;
            }
        }
    }

    public static int maxEnvelopes(int[][] es) {
        if(es == null || es.length == 0
                || es[0] == null || es[0].length != 2)
            return 0;
        Dot[] dots = new Dot[es.length];
        for (int i = 0; i < es.length; i++) {
            dots[i] = new Dot(es[i][0], es[i][1]);
        }
        Arrays.sort(dots, new DotComparator());
        int[] h = new int[es.length];
        h[0] = dots[0].h;
        int hl = 0;
        int r = 0;
        int l = 0;
        int mid = 0;
        for (int i = 1; i < dots.length; i++) {
            r = hl;
            l = 0;
            while (l <= r) {
                mid = (l + r) / 2;
                if (h[mid] < dots[i].h) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            hl = Math.max(hl, l);
            h[l] = dots[i].h;
        }
        return hl + 1;
    }

    public static void main(String[] args) {
        int es[][] = {{4, 5}, {4, 6}, {6, 7}, {2, 3}, {1, 1}};
        System.out.println(maxEnvelopes(es));
    }

}
